//给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。 
//
// 返回符合要求的 最少分割次数 。 
//
// 
// 
// 
//
// 示例 1： 
//
// 
//输入：s = "aab"
//输出：1
//解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
// 
//
// 示例 2： 
//
// 
//输入：s = "a"
//输出：0
// 
//
// 示例 3： 
//
// 
//输入：s = "ab"
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 2000 
// s 仅由小写英文字母组成 
// 
// 
// 
// Related Topics字符串 | 动态规划 
//
// 👍 621, 👎 0 
//
//
//
//

package leetcode.editor.cn;

class PalindromePartitioningIi {
    public static void main(String[] args) {
        Solution solution = new PalindromePartitioningIi().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int minCut(String s) {
            int n = s.length();
            boolean[][] isPalindromic = new boolean[n][n];
            for (int i = n - 1; i >= 0; i--) {
                for (int j = i; j < n; j++) {
                    if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || isPalindromic[i + 1][j - 1] )) {
                        isPalindromic[i][j] = true;
                    }
                }
            }

            // 表示[0,i]切分为回文子串的最小切分次数
            int[] dp = new int[n];
            // 初始化，最多分割次数为当前长度 - 1
            for (int i = 0; i < n; i++) dp[i] = i;
            for (int i = 1; i < n; i++) {
                // 如果[0,i]是回文子串，那么分割的次数为0
                if (isPalindromic[0][i]) {
                    dp[i] = 0;
                    continue;
                }

                for (int j = 0; j < i; j++) {
                    // wrong错误判断，因为不是回文子串也能被切分为回文子串
                    // 如果[0,j]不是回文子串，那么无法切分
                    // if (!isPalindromic[0][j]) continue;

                    // 如果[0,j]和[j,i]都是回文子串，那么可以进行拆分
                    if (isPalindromic[j + 1][i]) {
                        dp[i] = Math.min(dp[i], dp[j] + 1);
                    }
                }
            }

            return dp[n - 1];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
